package com.zhugang.week13.sorting;

import java.util.List;

import static java.util.stream.Collectors.toList;

/**
 * @program algorithms
 * @description: quickSort
 * @author: chanzhugang
 * @create: 2022/09/30 23:53
 */
public class QuickSort implements IIMutableSorter {

    /**
     * 快排
     *
     * @param A
     * @return
     */
    @Override
    public List<Integer> sort(List<Integer> A) {
        return quickSort(A);
    }

    private List<Integer> quickSort(List<Integer> A) {
        if (A.size() <= 1) {
            return A;
        }
        // 小于val的放左边；大于val的放右边
        int val = A.get(0);
        // 流式编程：和第一个元素比较
        List<Integer> left = A.stream().filter(a -> a < val).collect(toList());
        List<Integer> mid = A.stream().filter(a -> a == val).collect(toList());
        List<Integer> right = A.stream().filter(a -> a > val).collect(toList());
        // 递归
        left = sort(left);
        right = sort(right);

        left.addAll(mid);
        left.addAll(right);
        return left;
    }
}